//
// Description: 5809. 长度为 3 的不同回文子序列
// Created by Loading on 2021/7/11.
//

#include <bits/stdc++.h>

using namespace std;

int countPalindromicSubsequence(string s) {
    long long res = 0;
    unordered_set<char> S;
    /* 长度为 3 的回文子序列，则首尾两个字母是一致的，首尾两个字母最多有 26 种情况 */
    for (int index = 0; index < 26; ++index) {
        //遍历 26 个字母
        char c = index + 'a';
        S.clear();
        for (int i = 0, j = s.size() - 1; j - i > 1;) {
            //找到首尾字母与当前字母相同
            if (s[i] == c && s[j] == c) {
                //遍历这两个字母之间的其他字母，使用 hashset 储存，保证不重复
                for (int k = i + 1; k < j; ++k) {
                    S.insert(s[k]);
                }
                break;
            }
            //未找到，继续寻找
            if (s[i] != c) {
                ++i;
            }
            if (s[j] != c) {
                --j;
            }
        }
        //累计结果
        res += S.size();
    }

    return res;
}

int main() {
    string s = "aabca";
    cout << countPalindromicSubsequence(s) << endl;
}